Permutation / Ladder lottery (Bibtex)

P44: Enumeration of all optimal ladder lotteries

Input:

A permutation.

Output:

All optimal ladder lotteries with satisfying the permutation.

Complexity:

$O(1)$ time per solution on average, $O(n^2)$ space, and $O(n^2)$ time preprocessing.

Comment:

$n$ is the length of the input permutation. We call a ladder lottery is an optimal when the number of horizontal lines in the ladder lottery is minimum. Ladder lotteries are also known as arrangements of pseudolines.

Reference:

[Yamanaka2010] (Bibtex)

P169: Enumeration of all ladder lotteries with $k$ bars

Input:

A permutation $\pi$ and integer $k$.

Output:

All ladder lotteries of $\pi$ with $k$ bars.

Complexity:

$O(1)$ time per ladder lottery.

Comment:

Ladder lotteries are also known as \textit{Amida kuji} in Japan.

Reference:

[Yamanaka2014] (Bibtex)